#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <queue>
#include <stack>
#include <vector>
#include <iostream>
using namespace std;

#define VertexType char
#define InfoType int
#define MaxVertexNum 20

// 结构体定义
typedef struct ArcNode
{
    int adjVex;           // 边/弧指向哪个结点
    struct ArcNode *next; // 指向下一条弧的指针
    // InfoType info;        // 边权值
} ArcNode;           // 边
typedef struct VNode // 顶点
{
    VertexType data; // 顶点信息，如果该顶点未插入，则信息为0
    ArcNode *first;  // 第一条边/弧
} VNode, AdjList[MaxVertexNum];
typedef struct
{
    AdjList vertices;   // 结点,从0开始
    int vexNum, arcNum; // vexNum:结点数, arcNum:边数
    bool directed;      // true:有向图,false:无向图
} ALGraph;              // 用领接表存储的图

// 常用操作
void Adjacent(ALGraph *G, int x, int y);                       // 判断图G是否存在边<x，y>或(x，y)。
void Neighbors(ALGraph *G, int x);                             // 列出图G中与结点x邻接的边。
void InsertVertex(ALGraph *G, int x);                          // 在图G中插入顶点x。
void DeleteVertex(ALGraph *G, int x);                          // 从图G中删除顶点x。
void AddEdge(ALGraph *G, int x, int y);                        // 若无向边(x，y)或有向边<x,y>不存在，则向图G中添加该边。
void RemoveEdge(ALGraph *G, int x, int y);                     // 若无向边(x, y)或有向边<x，y>存在，则从图G中删除该边。
int FirstNeighbor(ALGraph *G, int x);                          // 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回 - 1。
int NextNeighbor(ALGraph *G, int x, int y);                    // 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的项点号，若y是x的最后一个邻接点，则返回 - 1。
InfoType Get_edge_value(ALGraph *G, int x, int y);             // 获取图G中边(x, y)或<x,y>对应的权值。
InfoType Set_edge_value(ALGraph *G, int x, int y, InfoType v); // 设置图G中边(x，y)或<x,y>对应的权值为v。
void Visit(int v);                                             // 访问图结点
void InitALGraph(ALGraph *G);                                  // 初始化领接表
void CreateALGraph(ALGraph *G);                                // 创建领接表存储图
bool visited[MaxVertexNum];                                    // 访问标记数组
queue<int> Q;                                                  // C++STL创建队列Q

// BFS广度优先遍历算法
void BFSTraverse(ALGraph *G); // 对图G进行广度优先遍历
void BFS(ALGraph *G, int v);  // 从顶点V出发，广度优先遍历G

// DFS深度优先遍历算法
void DFSTraverse(ALGraph *G); // 对图G进行深度优先遍历
void DFS(ALGraph *G, int v);  // 从顶点V出发，广度优先遍历G

// BFS最短路径算法
int d[MaxVertexNum];                      // d[i]表示从u到i结点的最短路径长度
int path[MaxVertexNum];                   // path[i]表示最短路径中的上一个顶点
void BFS_MIN_DISTANCE(ALGraph *G, int u); // 无向图中求顶点u到其他顶点的最短路径

// 拓扑排序
void TopologicalSort(ALGraph *G);             // 拓扑排序（有向图）
int count = 0;                                // 记录已经输出结点的个数
int print[MaxVertexNum] = {-1};               // 记录输出序列
int Visited[MaxVertexNum] = {-1};             // -1表示未被访问，0表示正在访问，1表示访问过了
bool ring_exist = false;                      // 环存在标识
void DFSTraverse_TopologicalSort(ALGraph *G); // DFS算法实现逆向拓扑排序
void DFS_TopologicalSort(ALGraph *G, int v);  // DFS算法实现逆向拓扑排序

int main()
{
    ALGraph G;
    CreateALGraph(&G);
    // BFSTraverse(&G);
    // DFSTraverse(&G);

    // TopologicalSort(&G);

    DFSTraverse_TopologicalSort(&G);
    return 0;
}
void InsertVertex(ALGraph *G, int x) // 在图G中插入顶点x。
{
    assert(G != NULL);
    if (G->vertices[x].data == 0)
        G->vexNum++;
    G->vertices[x].data = x + 'A';
    return;
}
void DeleteVertex(ALGraph *G, int x) // 从图G中删除顶点x。
{
    assert(G != NULL);
    if (G->vertices[x].data == 0)
        return;
    G->vertices[x].data = 0;
    ArcNode *temp = G->vertices[x].first;
    while (temp != NULL)
    {
        ArcNode *tmp = temp;
        if (G->directed == false)
        {
            // 删除<?,x>
            ArcNode *tmp1 = G->vertices[temp->adjVex].first;
            if (tmp1->adjVex == x)
            {
                G->vertices[temp->adjVex].first = tmp1->next;
                free(tmp1);
                tmp1 = NULL;
            }
            else
            {
                while (tmp1->next->adjVex != x) // 让tmp2偏移到指向x的前一个
                {
                    tmp1 = tmp1->next;
                }
                ArcNode *tmp2 = tmp1->next;
                tmp1->next = tmp1->next->next;
                free(tmp2);
                tmp2 = NULL;
            }
        }
        temp = temp->next;
        free(tmp); // 删除<x,?>
        G->arcNum--;
    }
    if (G->directed == true)
        for (int i = 0; i < G->vexNum; i++)
        {
            if (i != x)
            {
                temp = G->vertices[i].first;
                if (temp->adjVex == x)
                {
                    G->vertices[i].first = temp->next;
                    free(temp);
                    G->arcNum--;
                    temp = NULL;
                }
                else if (temp != NULL)
                    while (temp->next != NULL)
                    {
                        if (temp->next->adjVex == x)
                        {
                            ArcNode *tmp = temp->next;
                            temp->next = temp->next->next;
                            free(tmp);
                            G->arcNum--;
                            tmp = NULL;
                            break;
                        }
                    }
            }
        }
    G->vexNum--;
    return;
}
void AddEdge(ALGraph *G, int x, int y) // 若无向边(x，y)或有向边<x,y>不存在，则向图G中添加该边。
{
    assert(G != NULL);
    ArcNode *temp = G->vertices[x].first;
    while (temp != NULL) // 检查是否存在(x,y)或<x,y>
    {
        if (temp->adjVex == y)
            return;
        temp = temp->next;
    }
    temp = G->vertices[x].first; // 头插法
    G->vertices[x].first = (ArcNode *)malloc(sizeof(ArcNode));
    G->vertices[x].first->adjVex = y;
    G->vertices[x].first->next = temp;
    if (G->directed == false)
    {
        temp = G->vertices[y].first;
        G->vertices[y].first = (ArcNode *)malloc(sizeof(ArcNode));
        G->vertices[y].first->adjVex = x;
        G->vertices[y].first->next = temp;
    }
    G->arcNum++;
    return;
}
void RemoveEdge(ALGraph *G, int x, int y) // 若无向边(x, y)或有向边<x，y> 存在，则从图G中删除该边。
{
    assert(G != NULL);
    bool existFlag = false;
    assert(G->vertices[x].first != NULL);
    ArcNode *temp = G->vertices[x].first; // 先删<x,y>
    if (temp->adjVex == y)                // y为x的第一个邻接点
    {
        G->vertices[x].first = temp->next;
        existFlag = true;
    }
    else
        while (temp->next != NULL)
        {
            if (temp->next->adjVex == y)
            {
                ArcNode *tmp = temp->next;
                temp->next = temp->next->next;
                free(tmp);
                G->arcNum--;
                tmp = NULL;
                existFlag = true;
                break;
            }
            temp = temp->next;
        }
    if (!existFlag || G->directed == true)
        return;
    temp = G->vertices[y].first; // 再删(y,x)
    if (temp->adjVex == x)       // x为y的第一个邻接点
    {
        G->vertices[y].first = temp->next;
    }
    else
        while (temp->next != NULL)
        {
            if (temp->next->adjVex == x)
            {
                ArcNode *tmp = temp->next;
                temp->next = temp->next->next;
                free(tmp);
                tmp = NULL;
                break;
            }
            temp = temp->next;
        }
}
int FirstNeighbor(ALGraph *G, int x) // 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回 - 1。
{
    assert(G != NULL);
    ArcNode *temp = G->vertices[x].first;
    if (temp == NULL)
        return -1;
    return temp->adjVex;
}
int NextNeighbor(ALGraph *G, int x, int y) // 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的项点号，若y是x的最后一个邻接点，则返回 - 1。
{
    assert(G != NULL);
    ArcNode *temp = G->vertices[x].first;
    while (temp != NULL)
    {
        if (temp->adjVex == y)
        {
            if (temp->next == NULL)
                return -1;
            else
                return temp->next->adjVex;
        }
        temp = temp->next;
    }
}
void InitALGraph(ALGraph *G) // 初始化领接表
{
    assert(G != NULL);
    int i = 0;
    for (i = 0; i < MaxVertexNum; i++)
    {
        G->vertices[i].data = 0;
        G->vertices[i].first = NULL;
    }
    G->vexNum = 0;
    G->arcNum = 0;
    return;
}
void CreateALGraph(ALGraph *G) // 创建领接表存储图
{
    assert(G != NULL);
    InitALGraph(G);
    int i = 0;
    printf("Directed(1) or undirected(0)?\n");
    scanf("%d", &i);
    if (i == 1)
        G->directed = true;
    else
        G->directed = false;
    printf("How many vertices do you want to insert?(0~20)\n");
    scanf("%d", &i);
    int j = 0;
    for (j = 0; j < i; j++)
    {
        InsertVertex(G, j);
    }
    printf("Enter the arcs.Enter\"x y\"to add (x,y) or <x,y>.Enter -1 to come an end\n");
    int x, y;
    scanf("%d", &x);
    while (x != -1)
    {
        scanf("%d", &y);
        AddEdge(G, x, y);
        scanf("%d", &x);
    }
}
void BFSTraverse(ALGraph *G) // 对图G进行广度优先遍历
{
    assert(G != NULL);
    for (int i = 0; i < G->vexNum; i++)
    {
        visited[i] = false; // 访问标记数组初始化
    }
    // InitQueue(Q); // 初始化辅助队列

    for (int i = 0; i < G->vexNum; i++)
    {
        if (!visited[i]) // 对每个连通分量调用一次BFS
            BFS(G, i);   // vi未访问过，从vi开始BFS
    }
}
void Visit(int v)
{
    printf("%d ", v);
}
void BFS(ALGraph *G, int v) // 从顶点V出发，广度优先遍历G
{
    assert(G != NULL);
    Visit(v); // 访问初始顶点v
    printf("\n");
    visited[v] = true; // 对v做已访问标记
    Q.push(v);         // v入队Q
    while (!Q.empty())
    {
        v = Q.front(); // v等于队首元素
        Q.pop();       // 出队
        int flag = 0;
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) // 检测所有邻接点
        {
            if (!visited[w]) // w为v尚未访问的邻接点
            {
                Visit(w); // 访问结点w
                flag = 1;
                visited[w] = true; // 标记W
                Q.push(w);         // 出队
            }
        }
        if (flag)
            printf("\n");
    }
}
void DFSTraverse(ALGraph *G) // 对图G进行深度优先遍历
{
    int i = 0;
    for (i = 0; i < G->vexNum; i++)
    {
        visited[i] = false;
    }
    for (i = 0; i < G->vexNum; i++)
    {
        if (!visited[i])
        {
            DFS(G, i);
            printf("\n");
        }
    }
    return;
}
void DFS(ALGraph *G, int v) // 从顶点V出发，广度优先遍历G
{
    Visit(v);
    visited[v] = true;
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    {
        if (!visited[w])
            DFS(G, w);
    }
    return;
}
void BFS_MIN_DISTANCE(ALGraph *G, int u) // 无向图中求顶点u到其他顶点的最短路径
{
    int i = 0;
    for (int i = 0; i < G->vexNum; i++)
    {
        visited[i] = false; // 访问标记数组初始化
    }
    Q = queue<int>(); // 清空队列
    for (i = 0; i < G->vexNum; i++)
    {
        d[i] = INT_MAX; // 初始化路径长度
        path[i] = -1;   // 最短路径从哪个顶点过来
    }
    d[u] = 0;
    visited[u] = true;
    Q.push(u);
    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
        {
            if (!visited[w])
            {
                d[w] = d[u] + 1;
                path[w] = u;
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}
void TopologicalSort(ALGraph *G) // 拓扑排序（有向图）
{
    int v = 0, w = 0;
    stack<int> stk;
    vector<int> in_degree(G->vexNum, 0); // 记录顶点入度
    for (v = 0; v < G->vexNum; v++)      // 计算所有顶点入度
    {
        print[v] = -1; // 初始化输出序列
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        {
            in_degree[w]++;
        }
    }
    for (v = 0; v < G->vexNum; v++)
    {
        if (in_degree[v] == 0)
            stk.push(v);
    }
    count = 0; // 记录已经输出结点的个数
    while (!stk.empty())
    {
        v = stk.top();
        stk.pop();
        print[count++] = v; // 输出栈顶
        // in_degree[v]--;     // 已删除顶点的入度记为-1
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        {
            if (--in_degree[w] == 0)
                stk.push(w);
        }
    }
    if (count == G->vexNum) // 拓扑排序成功
    {
        for (v = 0; v < count; v++)
        {
            printf("%d", print[v]);
            if (v == count - 1)
                printf("\n");
            else
                printf("->");
        }
        return;
    }
    else // count < G->vexNum 说明有环，排序失败
    {
        printf("Ring exist!\n");
        return;
    }
}
void DFSTraverse_TopologicalSort(ALGraph *G) // DFS算法实现逆向拓扑排序
{
    ring_exist = false;
    int v = 0;
    count = 0;
    for (v = 0; v < G->vexNum; v++)
    {
        Visited[v] = -1;
        print[v] = -1; // 初始化输出序列
    }
    for (v = 0; v < G->vexNum; v++)
    {
        if (Visited[v] == -1)
            DFS_TopologicalSort(G, v);
        // else if (Visited[v] == 0)
        // {
        //     ring_exist = true;
        //     break;
        // }
    }
    if (ring_exist)
    {
        printf("Ring exists!\n");
        return;
    }
    else
    {
        for (v = 0; v < count; v++)
        {
            printf("%d", print[v]);
            if (v == count - 1)
                printf("\n");
            else
                printf("->");
        }
    }
}
void DFS_TopologicalSort(ALGraph *G, int v) // DFS算法实现逆向拓扑排序
{
    int w = 0;
    Visited[v] = 0;
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    {
        if (Visited[w] == -1)
            DFS_TopologicalSort(G, w);
        else if (Visited[w] == 0)
        {
            ring_exist = true;
            break;
        }
    }
    print[count++] = v;
    Visited[v] = 1;
}
